package com.echo.boot.structure.trie;

import java.util.HashMap;

/**
 * Created with IntelliJ IDEA
 * Created By CQ
 * Date: 2020/6/18
 * Time: 10:35
 * 字典树
 *
 * @author Administrator
 */
public class Trie<V> {
    private int size;

    private Node<V> root;

    private static class Node<V> {
        Node<V> parent;
        HashMap<Character, Node<V>> children;
        Character character;
        V value;
        boolean word;

        public Node(Node<V> parent) {
            this.parent = parent;
        }
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        size = 0;
        root = null;
    }

    public V add(String key, V value) {
        keyCheck(key);
        if (root == null) {
            root = new Node(null);
        }
        Node<V> node = root;
        int len = key.length();
        for (int i = 0; i < len; i++) {
            char c = key.charAt(i);
            // map 是否为空
            boolean emptyChildren = (node.children) == null;
            // 如果map 为空 就 null,不为空 取出 map元素
            Node<V> childNode = emptyChildren ? null : node.children.get(c);
            // 如果 map 中 没有找到 元素
            if (childNode == null) {
                // 创建  新的节点, 根节点为父节点
                childNode = new Node(node);
                childNode.character = c;
                // 第一次出现, 创建 map,把 子节点 放入 map; 已有直接put 以 char 为 key, node 为 值 放入 map
                node.children = emptyChildren ? new HashMap<>() : node.children;
                // map 一个字符 对应一个 节点
                node.children.put(c, childNode);
            }
            node = childNode;
        }
        // 循环结束
        // 已经存在这个单词
        if (node.word) {
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }

        // 新增加一个单词
        node.word = true;
        node.value = value;
        size++;

        return null;
    }

    public V get(String key) {
        Node<V> node = node(key);
        return (node != null && node.value != null) ? node.value : null;
    }

    public boolean contains(String key) {
        Node<V> node = node(key);
        return node != null && node.word;
    }


    public V remove(String key) {
        // 找到最后一个节点
        Node<V> node = node(key);
        // 如果不是单词结尾不做任何处理
        if (node == null || !node.word) {
            return null;
        }

        V oldValue = node.value;
        // 如果还有子节点
        if (node.children != null && !node.children.isEmpty()) {
            // 修改 标记单词结尾  为 false
            node.word = false;
            // 把 value 清空
            node.value = null;
            return oldValue;
        }
        // 如果没有子节点
        Node<V> parent = null;
        while ((parent = node.parent) != null) {
            // 父节点 的 map 把自己 删除掉
            parent.children.remove(node.character);
            // 如果父节点的map 是其他单词结尾 或者 还包含其他元素,退出循环
            if (parent.word || !parent.children.isEmpty()) {
                break;
            }
            node = parent;
        }
        size--;
        return oldValue;
    }

    public boolean startsWith(String prefix) {
        return node(prefix) != null;
    }

    private void keyCheck(String key) {
        if (key == null || key.length() == 0) {
            throw new IllegalArgumentException("key must not be empty");
        }
    }


    private Node<V> node(String key) {
        keyCheck(key);
        Node<V> node = root;
        int len = key.length();
        for (int i = 0; i < len; i++) {
            // 如果 节点是null,或者 节点的map为 null, map的长度为 0
            if (node == null || node.children == null || node.children.isEmpty()) {
                return null;
            }
            char c = key.charAt(i);
            node = node.children.get(c);
        }
        return node;
    }
}
